1. Field of the Invention
The present invention relates in general to computers, and more particularly to methods, computer systems, and computer program products for computation of a remainder by division of a sequence of bytes using pseudo-remainders.
2. Description of the Related Art
In many contexts, it is necessary to compute the remainder obtained by the division of a very large number by a smaller number that is close to a power of 2. As an example, in the case of some Rabin-Karp hash functions, it is necessary to compute the remainder obtained by the division of a 512-byte number by a constant 7-byte prime number such as 255−55.
Most programming languages have built-in operations for calculating such remainders, the modulo operation, but this obviously works only on inputs of restricted length (typically 32, 64 or 128 bits). For much larger numbers, as those represented by an input bit string of a priori unlimited length, the operation has to be performed iteratively. For instance, the traditional iterative computation of the remainder of the division of a 512-byte number contained in an array “buf” by a smaller number P is:
                              h          =          0                ;                  for          ⁢                                          ⁢                      (                                          i                =                0                            ;                              i                <                512                            ;                              i                ++                                      )                    ⁢                      {                                          h                =                                                      (                                                                  h                        *                                                  2                          8                                                                    +                                              buf                        ⁡                                                  [                          i                          ]                                                                                      )                                    ⁢                                                                          ⁢                  %                  ⁢                                                                          ⁢                  P                                            ;                        }                    ⁢                                          ⁢          return          ⁢                                          ⁢          h                ;                            (        1        )            
This traditional computation uses 512 steps to compute the remainder. In each traditional step, a new value of the intermediate result h is computed by taking the previous value of the intermediate product, multiplying it by 256, adding the next byte from the 512-byte number, and then taking the remainder of this number when divided by P. This solution requires significant computing resources.
To reduce the number of steps, one could increase the number of bytes processed in each iteration. For example, if 4 bytes are processed in each iteration instead of 1, the procedure will become
h = 0;for (i=0; i < 512; i+=4) { h = (h * 232 + buf[i]<<24 + buf[i]<<16 + buf[i]<<8 + buf[i]) % P;}return h;
Increasing the size of the basic unit to be processed to 4 bytes may produce intermediate calculations which exceed the capacity of the largest integers that can be handled efficiently.